Shannon 编码定理_信源编码定理

Shannon 编码定理

信源编码定理

在信息论中，香农的信源编码定理（或无噪声编码定理）确立了数据压缩的限度，以及香农熵的操作意义。

陈述

信源编码是从信息源的符号（序列）到码符号集（通常是bit）的映射，使得信源符号可以从二进制位元（无损信源编码）或有一些失真（有损信源编码）中准确恢复。这是在数据压缩的概念。

信源编码定理

在信息论中，信源编码定理非正式地陈述为：

N个熵均为H(X)的独立同分布的随机变量在N→∞时，可以很小的信息损失风险压缩成多于N H(X)bit；但相反地，若压缩到少于 bit，则信息几乎一定会丢失。

码符号的信源编码定理

令Σ1,Σ2表示两个有限编码表，并令Σ1*和Σ2*（分别）表示来自那些编码表的所有有限字的集合。

设X为从Σ1取值的随机变量，令 f 为从Σ1*到Σ2*的唯一可译码，其中|Σ2|=a。令S表示字长 f (X)给出的随机变量。

如果 f 是对X拥有最小期望字长的最佳码，那么：

证明：码符号的信源编码定理

对于1≤i≤n令si表示每个可能的xi的字长。定义，其中C会使得q1+...+qn=1。于是

其中第二行由吉布斯不等式推出，而第五行由克拉夫特不等式推出：

因此logC≤0。

对第二个不等式我们可以令

于是

因此

并且

因此由克拉夫特不等式，存在一种有这些字长的无前缀编码。因此最小的S满足

参考资料

最新修订时间：2022-08-26 10:20

条目作者

概述

陈述

参考资料